
public class Heap 
{
	public int array[];
	public int length;

	public void swap(int i, int j) 
	{
		int tmp = array[i];
		array[i]=array[j];
		array[j]=tmp;
	}
	
	public void buildHeap()
	{
		while(length != 0)
		{
			for(int i = (length - 1)/2; i >= 0; i--)
				maxHeap(i);
			swap(0,length-1);
			length--;
		}
	}
	
	public void maxHeap(int parent)
	{
		int right = 2 * parent + 2;
		int left = 2 * parent + 1;
		
		int biggest = parent;
		if(right < length && array[right] > array[biggest])
			biggest = right;
		if(left < length && array[left] > array[parent])
			biggest = left;
		
		
		
		if(biggest!=parent)
		{
			swap(parent, biggest);
			maxHeap(biggest);
		}
	}

	public Heap(int length)
	{                    
		this.length = length;                   
		array = new int[length];
		for(int i = 0; i < length; i++)
			array[i] = (int)(Math.random()*100);
	}

	public static void main(String[] args) {
		int N = 1000;
		double start;
		double stop;
		
		for(int i=0; i<10; i++)
		{
			System.out.print("Size array - " + N +"   ");
			Heap hs = new Heap(N);
			start = System.nanoTime()/10000000;
			hs.buildHeap();
			stop = System.nanoTime()/10000000;
			System.out.println("Time - " + (stop-start) + "mls");
			N=N+1000;
		}
	}

}
